/******************************************************************************
Filename        : main.c
Author          : YX
Date            : 10/16/2021
License         : The Unlicense
Description     : 找出图中含有K个节点的团。所谓K节点团就是指含有K个点子图，并且这K个点每两两相连。
Algorithm Hints : 找出K-1个节点的团，再对所有点找出第K个节点，使得它和前面的K-1节点团构成新的团
******************************************************************************/

/* Includes ******************************************************************/
#include <stdio.h>
/* End Includes **************************************************************/

/* Defines ******************************************************************/
/* 线段数量 */
#define NUM_LINES       22
#define MAX_CLIQUE_NUM  100
/* End Defines **************************************************************/

/* Begin Function: _Quick_Sort_Partition ************************************************
Description      :  Quick Sort Partition函数，不是该程序关键，介绍省略
**********************************************************************************/
int _Quick_Sort_Partition(int Array[], int Low, int High)
{
    int Piviot = Array[High];
    int I_Cnt = Low - 1;
    int J_Cnt = Low;
    int tmp;
    for ( ; J_Cnt <= High - 1; J_Cnt++ )
    {
        if( Array[J_Cnt] < Piviot )
        {
            I_Cnt++;
            tmp = Array[I_Cnt];
            Array[I_Cnt] = Array[J_Cnt];
            Array[J_Cnt] = tmp;
        }
    }

    if (Array[High] < Array[I_Cnt + 1])
    {
        tmp = Array[I_Cnt + 1];
        Array[I_Cnt + 1] = Array[High];
        Array[High] = tmp;
    }
    return I_Cnt + 1;
}
/* End Function: _Quick_Sort_Partition **************************************************/

/* Begin Function: Quick_Sort ************************************************
Description      : 快速排序算法，不是该程序关键，介绍省略
**************************************************************************/
void Quick_Sort(int Array[], int Low, int High)
{
    int Partion_Point;
    if (Low < High)
    {
        Partion_Point = _Quick_Sort_Partition(Array, Low, High);
        Quick_Sort(Array, Low, High - 1);
        Quick_Sort(Array, Partion_Point + 1, High);
    }
}
/* End Function: Quick_Sort **************************************************/

/* Begin Function: Check_Elem_Exist *********************************************
Description : 判断一个元素是否在一个数组里
Input       : int Array[]   - 被查找的目标数组
              int Num_Elem  - 数组总共的元素个数
              int Elem      - 要查找的元素值
Output      : 无
Return      : 0表示没有找到，1表示找到
******************************************************************************/
int Check_Elem_Exist(int Array[], int Num_Elem, int Elem)
{
    int I_Cnt;
    for ( I_Cnt = 0; I_Cnt < Num_Elem; I_Cnt++)
    {
        if (Array[I_Cnt] == Elem)
        {
            return 1;
        }
    }
    return 0;
}
/* End Function: Check_Elem_Exist **************************************************/

/* Begin Function: Find_K_Cliques *********************************************
Description   : 找出所有的K节点团
Input         : int Lines[][2]       - 线段二维数组
                int Num_Lines        - 总共线段的数目
                int K                - K节点团所对应的K
Output        : int K_Cliques[][K]   - 所有K节点团的节点信息，二维数组
Return        : 0表示没有找到，>0表示找到了K节点团，且该数字为K节点团的数量
******************************************************************************/
int Find_K_Cliques(int Lines[][2], int Num_Lines, int K, int K_Cliques[][K])
{
    int I_Cnt;                                      /* 第一次循环 */
    int J_Cnt;                                      /* 第二次循环 */
    int K_Cnt;                                      /* 第三次循环 */
    int M_Cnt;                                      /* 第四次循环 */
    int Old_Cliques[MAX_CLIQUE_NUM][K-1];           /* 用来存放上一次k-1次返回的cliques */
    int Old_Num_Cliques;                            /* 用来存放上一次k-1返回的cliques的个数 */
    int Count_Connected_Nodes_Num = 0;              /* 用来存放Candidate与K-1 Cliques相连的节点的个数 */
    int Record_Index = 0;                           /* 记录K_Cliques存到第几条 */
    int Found = 0;                                  /* 表示是否找到clique的计数器 */
    int Duplicate = 0;                              /* 赋值K_Cliques查重的flag */
    int Candidate_Node = 0;                         /* 候选节点，用于暂时存放第一次找到相同的节点线段的另一个节点 */
    int Clique_Nodes[K];                            /* 用来存储每次循环得到的团的K个节点 */

    /* K小于2，团没有意义，返回0 */
    if ( K < 2 )
    {
        return 0;
    }

    /* K是2的时候，团就是线段 */
    if ( K == 2 )
    {
        for ( I_Cnt = 0; I_Cnt < Num_Lines; I_Cnt++ )
        {
            K_Cliques[I_Cnt][0] = Lines[I_Cnt][0];
            K_Cliques[I_Cnt][1] = Lines[I_Cnt][1];
        }
        return Num_Lines;
    }

    /* K > 2的时候 */
    else
    {
        /* 得到K-1 Cliques */
        Old_Num_Cliques = Find_K_Cliques(Lines, Num_Lines, K-1, Old_Cliques);

        /* 遍历所有的K-1 Cliques */
        for ( I_Cnt = 0; I_Cnt < Old_Num_Cliques; I_Cnt++)
        {
            /* 遍历所有的线段，看看有没有共同点 */
            for ( J_Cnt = 0; J_Cnt < Num_Lines; J_Cnt++ )
            {
                /* 每次循环前清零Candidate */
                Candidate_Node = 0;
                Count_Connected_Nodes_Num = 0;

                /* 遍历K-1 Cliques中所有的节点 */
                for ( K_Cnt = 0; K_Cnt < K - 1; K_Cnt++)
                {
                    /* 找到其中一个点相同, Candidate为赋值一个点 */
                    if( Old_Cliques[I_Cnt][K_Cnt] == Lines[J_Cnt][0] )
                    {
                        /* 另一个点必须不存在与K-1 clique中 */
                        if( !Check_Elem_Exist(Old_Cliques[I_Cnt], K-1, Lines[J_Cnt][1]) )
                        {
                            Candidate_Node = Lines[J_Cnt][1];
                            break;
                        }

                    }
                    else if ( Old_Cliques[I_Cnt][K_Cnt] == Lines[J_Cnt][1] )
                    {
                        if( !Check_Elem_Exist(Old_Cliques[I_Cnt], K - 1, Lines[J_Cnt][0]) )
                        {
                            Candidate_Node = Lines[J_Cnt][0];
                            break;
                        }
                    }
                }

                /* Candidate点不为0，看candidate是否K-1 cliques中所有点都相连 */
                if (Candidate_Node)
                {
                    /* 遍历所有线段 */
                    for ( M_Cnt = 0; M_Cnt < Num_Lines; M_Cnt++)
                    {
                        /* 找到一条线段含有Candidate */
                        if ( (Candidate_Node == Lines[M_Cnt][0]) )
                        {
                            /* 如果该线段的另一个节点在K-1 Clique里面，则对Count_Connected_Nodes_Num+1 */
                            if ( Check_Elem_Exist(Old_Cliques[I_Cnt], K-1, Lines[M_Cnt][1]) )
                            {
                                Count_Connected_Nodes_Num++;
                            }
                        }
                        else if ( ( Candidate_Node == Lines[M_Cnt][1] ) )
                        {
                            if ( Check_Elem_Exist(Old_Cliques[I_Cnt], K - 1, Lines[M_Cnt][0]) )
                            {
                                Count_Connected_Nodes_Num++;
                            }
                        }
                    }

                    /* 如果 Count_Connected_Nodes_Num 与 K-1相等，则是一个clique*/
                    if (Count_Connected_Nodes_Num == K - 1)
                    {
                        /* 先遍历一下K_Cliques看看记录存不存在，避免重复 */
                        for ( M_Cnt = 0; M_Cnt < Record_Index; M_Cnt++)
                        {
                            for( K_Cnt = 0; K_Cnt < K - 1; K_Cnt++)
                            {
                                /* 判断是否所有K-1个点都存在 */
                                if( Check_Elem_Exist(K_Cliques[M_Cnt], K, Old_Cliques[I_Cnt][K_Cnt]) )
                                {
                                    Found++;
                                }
                            }

                            /* 判断Candidate是否也重复 */
                            if( Check_Elem_Exist(K_Cliques[M_Cnt], K, Candidate_Node) )
                                {
                                    Found++;
                                }

                            /* 只有全部K个点都存在(包括Candidate)，才算找到了重复的记录 */
                            if(Found == K)
                            {
                                Duplicate = 1;
                            }
                            Found = 0;
                        }

                        /* 没有重复记录，保存Clique节点 */
                        if( !Duplicate )
                        {
                            /* 将节点信息循环赋值给Clique_Nodes */
                            for( K_Cnt = 0; K_Cnt < K - 1; K_Cnt++)
                            {
                                Clique_Nodes[K_Cnt] = Old_Cliques[I_Cnt][K_Cnt];
                            }
                            Clique_Nodes[K - 1] = Candidate_Node;

                            /* 进行一下排序，使得打印结果更加易读 */
                            Quick_Sort(Clique_Nodes,  0, K - 1);

                            /* 将Clique_Nodes复制给K_Cliques */
                            for( K_Cnt = 0; K_Cnt < K; K_Cnt++)
                            {
                                K_Cliques[Record_Index][K_Cnt] = Clique_Nodes[K_Cnt];
                            }
                            Record_Index++;
                        }
                        Duplicate = 0;
                    }
                }
            }
        }
    }
    return Record_Index;
}
/* End Function: Find_K_Cliques **************************************************/

/* Begin Function: main ******************************************************
Description : 主函数.
Input       : 无.
Output      : 无.
Return      : int - Returns a value to the OS.
******************************************************************************/
int main()
{
    /*  线段由二维数组组成，数组每一个元素都是二维，分别是线段的两个节点的id */
    /*  所有线段没有重复  */
     int Lines[NUM_LINES][2] =
     {
        {2, 3}, {1, 2}, {7, 5}, {3, 4}, {4, 6}, {4, 7}, {1, 3},
        {1, 5}, {5, 6}, {2, 5}, {6, 7}, {2, 7}, {3, 5}, {1, 4},
        {8, 1}, {9, 1}, {8, 9}, {3, 8}, {7, 1}, {9, 2}, {8, 2},
        {7, 3}
     };

    /* 用于存放所有3节点团的二维数组
     * 每个元素分别是相对应的团的所有节点 */
    int Triple_Cliques[NUM_LINES * NUM_LINES][3] = {{0}};

    /* 用于存放所有4节点团的二维数组
     * 每个元素分别是相对应的团的所有节点 */
    int Quad_Cliques[NUM_LINES * NUM_LINES][4] = {{0}};

    /* 用于存放所有5节点团的二维数组
     * 每个元素分别是相对应的团的所有节点 */
    int Penta_Cliques[NUM_LINES * NUM_LINES][5] = {{0}};

    int Num_Triple_Cliques, Num_Quad_Cliques, Num_Penta_Cliques, I_Cnt;

    /* 查找3节点团 */
    Num_Triple_Cliques = Find_K_Cliques(Lines, NUM_LINES, 3, Triple_Cliques);
    printf("找到以下3节点团:\n");
    for (I_Cnt = 0; I_Cnt < Num_Triple_Cliques; I_Cnt++)
    {
        printf("%d ---- %d ---- %d\n", Triple_Cliques[I_Cnt][0], Triple_Cliques[I_Cnt][1], Triple_Cliques[I_Cnt][2]);
    }

    /* 查找4节点团 */
    Num_Quad_Cliques = Find_K_Cliques(Lines, NUM_LINES, 4, Quad_Cliques);
    printf("\n找到以下4节点团:\n");
    for (I_Cnt = 0; I_Cnt < Num_Quad_Cliques; I_Cnt++)
    {
        printf("%d ---- %d ---- %d --- %d\n",
               Quad_Cliques[I_Cnt][0], Quad_Cliques[I_Cnt][1],
               Quad_Cliques[I_Cnt][2], Quad_Cliques[I_Cnt][3]);
    }

    /* 查找5节点团 */
    Num_Penta_Cliques = Find_K_Cliques(Lines, NUM_LINES, 5, Penta_Cliques);
    printf("\n找到以下5节点团:\n");
    for (I_Cnt = 0; I_Cnt < Num_Penta_Cliques; I_Cnt++)
    {
        printf("%d ---- %d ---- %d --- %d --- %d\n",
               Penta_Cliques[I_Cnt][0], Penta_Cliques[I_Cnt][1],
               Penta_Cliques[I_Cnt][2], Penta_Cliques[I_Cnt][3],
               Penta_Cliques[I_Cnt][4]);
    }

    return 0;
}
/* End Function: main *********************************************************/
